/*
 *      Filename: queue.c
 *       Version: 0.1.0
 *   Description: 栈模拟队列
 *
 *        Author: wuyaowei
 *          Date: 2020-07-06
 *
 */

#include <stdio.h>
#include <stdlib.h>
/*
 *
 *思路：
 *1.使用两个栈实现
 *2.in为入栈，out为出栈，入队列则为入in栈，若in栈满则报错。
 *3.出队列时先判断out栈，有数据则直接出对，否则将in栈全部入out栈后，再从out栈出。
 *4.判断空队列需要判断in、out栈是否都为空
 *
 */

#define MAXSIZE 100

typedef struct {
    int data[MAXSIZE];
    int top;
} Stack;

typedef struct {
    Stack in; 
    Stack out;
} MyQueue;

/** Initialize your data structure here. */

MyQueue* myQueueCreate() {
    MyQueue* queue = (MyQueue*)malloc(sizeof(MyQueue));
    queue->in.top = -1;
    queue->out.top = -1;
    return queue;
}

/**线性栈操作**/
int isStackEmpty(Stack s) {
	return (s.top == -1)? 1:0;
}

int isStackFull(Stack s) {
	return (s.top >= MAXSIZE)?1:0;
}

/** Push element x to the back of queue. */
void myQueuePush(MyQueue* obj, int x) {
    if (isStackFull(obj->in)) {
		printf("Queue is full!");
		return;
	}
	
	obj->in.data[++obj->in.top] = x;
}

/** Removes the element from in front of queue and returns that element. */
int myQueuePop(MyQueue* obj) {
    if (!isStackEmpty(obj->out)) {
		return obj->out.data[obj->out.top--];
	}
	
	while(!isStackEmpty(obj->in)) {
		obj->out.data[++obj->out.top] = obj->in.data[obj->in.top--];
	}
	
	return obj->out.data[obj->out.top--];
}

/** Get the front element. */
int myQueuePeek(MyQueue* obj) {
		 if (!isStackEmpty(obj->out)) {
		return obj->out.data[obj->out.top];
	}
	
	while(!isStackEmpty(obj->in)) {
		obj->out.data[++obj->out.top] = obj->in.data[obj->in.top--];
	}
	
	return obj->out.data[obj->out.top];
}

/** Returns whether the queue is empty. */
int myQueueEmpty(MyQueue* obj) {
    return ((obj->in.top == -1) && (obj->out.top == -1)) ? 1 : 0;
}

void myQueueFree(MyQueue* obj) {
    free(obj);
}

void main() {
    MyQueue* queue = myQueueCreate();
    myQueuePush(queue, 1);
    myQueuePush(queue, 2);
    myQueuePush(queue, 3);
    myQueuePush(queue, 4);
    printf("第一次pop:%d\n", myQueuePop(queue));
    printf("第二次pop:%d\n", myQueuePop(queue));
    printf("peek:%d\n", myQueuePeek(queue));
    printf("myQueueEmpty:%d\n", myQueueEmpty(queue));
}
